package ds.tree;

public class CompleteBinaryTree {

	private static class TreeNode{
		int value;
		TreeNode left = null;
		TreeNode right = null;
		
		TreeNode(int val){
			this.value = val;
		}
		
		public String toString(){
			return String.valueOf(value);
		}
	}
	public int height(TreeNode node){
		if(node == null){
			return 0;
		}
		return 1+ Math.max(height(node.left) , height(node.right)); 
	}
	public void iterateLevels(TreeNode node){
		if (node ==  null){
			return;
		}
		boolean isComplete = true;
		int height = height(node);
		for (int i = 1; i <= height; i++) {
			isComplete = levelOrderTraversal(node, i);
			if(!isComplete){
				break;
			}
		}
		System.out.println("is complete = " + isComplete );
	}
	public boolean levelOrderTraversal(TreeNode node , int level) {
		if(node == null) {
			return true;
		}
		if(level == 1 )	{
			if(node.left == null && node.right == null){
				return true;
			}
			if(node.left!=null){
				return true;
			}
			return false;
		}
		boolean isComplete = levelOrderTraversal(node.left,level-1);
		
		if(!isComplete)	{
			return isComplete;
		}
		
		isComplete = levelOrderTraversal(node.right,level-1);
		return isComplete;
	}
	private static TreeNode tree(){
		TreeNode A = new TreeNode(1);
		TreeNode B = new TreeNode(2);
		TreeNode C = new TreeNode(3);
		TreeNode D = new TreeNode(4);
		TreeNode E = new TreeNode(5);
		TreeNode F = new TreeNode(6);
		TreeNode G = new TreeNode(7);
		
		A.left = B;
		A.right = C;
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;
		
		return A;
	}
	
	public static void main(String[] args) {
		CompleteBinaryTree binaryTree = new CompleteBinaryTree();
		binaryTree.iterateLevels(tree());
	}

}
